LeetCode——两数相除

NO.29 两数相除中等

看了很多人的题解，学习到了很多。但是有些题解我不敢苟同，例如用long存储变量的题解，题目明确说明：我们环境只能存储32位有符号整数；需要用乘法改变正负号的题解，第一句就说了不能用乘法。。等等

思路一：二分法除数翻倍 被除数中有N个除数，那么商就是N(用减法来实现除法，新被除数=被除数-除数&商+=1)。如果每次被除数只减一个除数，虽然可以实现除法，但是效率太低，在leetcode上也会TLE。所以采用每次除数翻倍(商也不再是每次+1)的方法。

这道题的思路并不难，但是本题有很多细节需要注意和学习：

商的范围需要注意，小心溢出。这里可以采用先将除数和被除数转换成负数并且用负数商来进行运算，运算结束再根据除数和被除数原本的符号决定商的符号(负号直接返回，正号需要判断符号转变后是否溢出)。
如何得到商的符号：判断除数和被除数异或之后的符号即可。
如何获得相反数：反码+1=补码。分享一篇文章，对这里有疑惑的同学可以看看——补码(为什么按位取反再加一)

举个栗子，17/3，除数和被除数都转换为负数(反码+1=补码)，即-17/-3，先用-17-(-3)=-14，商+=-1；

除数翻倍-14-(-6)=-8，商+=-2；

除数翻倍，此时的除数-12<被除数-8，所以除数重置为-3；

继续-8-(-3)=-5，商+=-1；

除数翻倍，此时的除数-6<被除数-5，所以除数重置为-3；

继续-5-(-3)=-2，商+=-1；

除数翻倍，此时的除数-6<被除数-2，所以除数重置为-3；

但是初始的除数-3<被除数-2，所以计算结束。

最后根据除数和被除数原本的符号决定商的符号，结果应该是”正正得正”，判断此时的负数商符号转变后是否溢出，负数商不等于32位有符号整形最小值-2147483648，所以可以直接转换为正数，返回负数商的相反数。

public int divide(int dividend, int divisor) {
    if (divisor==0)throw new IllegalArgumentException();
    //将除数和被除数异或之后，得到商的符号
    boolean isPositive=(dividend^divisor)>=0;
    //将除数和被除数都转化为负数
    if (dividend>0)dividend=opposite(dividend);
    if (divisor>0)divisor=opposite(divisor);
    // 商用负数来表示，这样可以处理Integer.MIN_VALUE的情况
    int ans=0;
    while (dividend<=divisor){
        int tempDivisor=divisor;
        int count=-1;
        //这里注意需要对tempDivisor是否为负数做判断，因为tempDivisor有可能会溢出
        while (tempDivisor<0&&dividend<=tempDivisor){
            //被除数-除数
            dividend-=tempDivisor;
            ans+=count;
            //除数翻倍
            tempDivisor+=tempDivisor;
            count+=count;
        }
    }
    //对返回值进行处理，这里也可以使用三目运算符完成
    if (isPositive){
        if (ans==Integer.MIN_VALUE){
            return Integer.MAX_VALUE;
        }else{
            return opposite(ans);
        }
    }else {
        return ans;
    }
}
//x的反码+1，得到x的相反数
private int opposite(int x){
    return ~x+1;
}

时间复杂度：O(logN)，除数是 1，每次减一个除数，我们将减 n 次，但因为每次除数都翻倍了，所以共减了log(n)次。

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.29 两数相除 中等

NO.29 两数相除中等